The compression encoding technology is used for efficiently performing transmission and storage of still image and dynamic image data. Widely used systems for dynamic images are MPEG-1 to 4 and ITU (International Telecommunication Union) H.261 to H.264.
In these encoding systems, an image as a target to be encoded is first divided into a plurality of blocks and then the encoding-decoding processing is carried out. In intra-picture predictive encoding, a prediction signal is generated using an adjacent previously-reproduced image signal (restored signal from compressed image data) present in the same picture as a target block, the generated prediction signal is subtracted from a signal of the target block to generate a residual signal, and the residual signal is then encoded. In inter-picture predictive encoding, a compensation for motion is made with reference to an adjacent previously-reproduced image signal present in a picture different from that of the target block, to generate a prediction signal, the prediction signal is subtracted from the signal of the target block to generate a residual signal, and the residual signal is then encoded.
For example, the intra-picture predictive encoding of H.264 adopts a method of extrapolating previously-reproduced pixel values adjacent to a block as a target of encoding in a predetermined direction to generate a prediction signal. FIG. 14 (FIG. 46) is a schematic diagram for explaining the intra-picture prediction method used in ITUH.264. In FIG. 14 (A) (FIG. 46 (A)), a target block 1702 is a block as a target of encoding and a pixel group 1701 consisting of pixels A to M adjacent to a border of the target block 1702 is an adjacent region and image signal reproduced previously in past processing.
In this case, the prediction signal is generated by extending the pixel group 1701 being adjacent pixels located immediately above the target block 1702, downwards. In FIG. 14 (B) (FIG. 46 (B)), the prediction signal is generated by extending previously-reproduced pixels (I to L) located left to the target block 1704, rightward. A difference is calculated between the pixel signal of the target block and each of nine prediction signals generated by the methods shown in FIG. 14 (A) (FIG. 46 (A) to (I) as described above, and the prediction signal to provide a minimum difference is defined as an optimal prediction signal. The prediction signals can be generated by extrapolating pixels as described above. The above contents are described in Patent Document 1 below.
In ordinary inter-picture predictive encoding, the prediction signal is generated by a method of, for a block as a target of encoding, searching a previously-reproduced picture for a signal similar to a pixel signal of the target block. Then encoded are a motion vector, which is a spatial displacement amount between the target block and a region composed of the signal obtained by the search, and a residual signal between the prediction signal and the pixel signal of the target block. The technique of searching for a motion vector for each block as described above is called block matching. FIG. 15 (or FIG. 47) is a schematic diagram for explaining the block matching processing. The below will describe a procedure of generating the prediction signal, using an example of target block 1402 on a picture 1401 as an encoding target. A picture 1403 in FIG. 15 (a) (or FIG. 47 (a)) is a previously-reproduced picture and a region 1404 indicated by a dashed line is a region located at the same spatial position as the target block 1402. In the block matching, a search region 1405 surrounding the region 1404 is first set, and a region 1406 is detected as one with a minimum sum of absolute differences from the pixel signal of the target block 1402 within the pixel signal of the search region. A pixel signal of the region 1406 is defined as a prediction signal and a displacement amount from the region 1404 to the region 1406 is detected as a motion vector. ITUH.264 prepares a plurality of prediction types with different block sizes for encoding of motion vector, in order to support variations of local characteristics of images. The prediction types of ITUH.264 are described, for example, in Patent Document 2.
In compression encoding of dynamic image data, an encoding order of frames is arbitrary. For the inter-picture prediction to generate the prediction signal with reference to the previously-reproduced picture, therefore, there are three types of techniques as to the encoding order. The first technique is forward prediction to generate the prediction signal with reference to a past reproduced picture in a reproduction order, the second technique backward prediction to generate the prediction signal with reference to a future reproduced picture in the reproduction order, and the third technique bidirectional prediction to perform both the forward prediction and backward prediction and average two prediction signals. The types of inter-picture prediction are described, for example, in Patent Document 3.    Patent Document 1: U.S. Pat. No. 6,765,964    Patent Document 2: U.S. Pat. No. 7,003,035    Patent Document 3: U.S. Pat. No. 6,259,739